package ar.com.utn.openqsb.lip.core;

import org.apache.commons.math.util.MathUtils;


public class SimplexSolver
{

    private static final double DEFAULT_EPSILON = 0.0000000001;
    protected final SimplexMatrix matrix;
    protected final double epsilon;

    /**
     * @param model
     *            the {@link SimplexModel} to solve.
     */
    public SimplexSolver(SimplexModel model)
    {
        this(model, true);
    }

    /**
     * @param model
     *            the {@link SimplexModel} to solve
     * @param nonNegative
     *            whether to restrict the variables to non-negative values
     */
    public SimplexSolver(SimplexModel model, boolean nonNegative)
    {
        this(model, nonNegative, DEFAULT_EPSILON);
    }

    /**
     * @param model
     *            the {@link SimplexModel} to solve
     * @param nonNegative
     *            whether to restrict the variables to non-negative values
     * @param epsilon
     *            the amount of error to accept in floating point comparisons
     */
    public SimplexSolver(SimplexModel model, boolean nonNegative, double epsilon)
    {
        this.matrix = new SimplexMatrix(model, nonNegative);
        this.epsilon = epsilon;
    }

    /**
     * Checks whether Phase 1 is solved.
     * 
     * @return whether Phase 1 is solved
     */
    private boolean isPhase1Solved()
    {
        if (!matrix.hasArtificialVariables())
        {
            return true;
        }
        for (int i = matrix.getNumObjectiveFunctions(); i < matrix.getWidth() - 1; i++)
        {
            if (matrix.getEntry(0, i) < 0)
            {
                return false;
            }
        }
        return true;
    }

    /**
     * Returns the column with the most negative coefficient in the objective
     * function row.
     */
    private Integer getPivotColumn()
    {
        double minValue = 0;
        Integer minPos = null;
        for (int i = matrix.getNumObjectiveFunctions(); i < matrix.getWidth() - 1; i++)
        {
            if (matrix.getEntry(0, i) < minValue)
            {
                minValue = matrix.getEntry(0, i);
                minPos = i;
            }
        }
        return minPos;
    }

    /**
     * Returns the row with the minimum ratio as given by the minimum ratio test
     * (MRT).
     * 
     * @param col
     *            the column to test the ratio of. See {@link #getPivotColumn()}
     */
    private Integer getPivotRow(int col)
    {
        double minRatio = Double.MAX_VALUE;
        Integer minRatioPos = null;
        for (int i = matrix.getNumObjectiveFunctions(); i < matrix.getHeight(); i++)
        {
            double rhs = matrix.getEntry(i, matrix.getWidth() - 1);
            if (matrix.getEntry(i, col) >= 0)
            {
                double ratio = rhs / matrix.getEntry(i, col);
                if (ratio < minRatio)
                {
                    minRatio = ratio;
                    minRatioPos = i;
                }
            }
        }
        return minRatioPos;
    }

    /**
     * Returns whether the problem is at an optimal state.
     * 
     * @return whether the model has been solved
     */
    public boolean isOptimal()
    {
        if (matrix.hasArtificialVariables())
        {
            return false;
        }
        for (int i = matrix.getNumObjectiveFunctions(); i < matrix.getWidth() - 1; i++)
        {
            if (matrix.getEntry(0, i) < 0)
            {
                return false;
            }
        }
        return true;
    }

    /**
     * Runs one iteration of the Simplex method on the given model.
     * 
     * @throws UnboundedSolutionException
     *             if the model is found not to have a bounded solution
     */
    protected void doIteration() throws UnboundedSolutionException
    {
        Integer pivotCol = getPivotColumn();
        Integer pivotRow = getPivotRow(pivotCol);
        if (pivotRow == null)
        {
            throw new UnboundedSolutionException();
        }

        // set the pivot element to 1
        double pivotVal = matrix.getEntry(pivotRow, pivotCol);
        matrix.divideRow(pivotRow, pivotVal);

        // set the rest of the pivot column to 0
        for (int i = 0; i < matrix.getHeight(); i++)
        {
            if (i != pivotRow)
            {
                double multiplier = matrix.getEntry(i, pivotCol);
                matrix.subtractRow(i, pivotRow, multiplier);
            }
        }
    }

    /**
     * Solves Phase 1 of the Simplex method.
     * 
     * @throws UnboundedSolutionException
     *             if the model is found not to have a bounded solution
     * @throws NoFeasibleSolutionException
     *             if there is no feasible solution
     */
    protected void solvePhase1() throws UnboundedSolutionException, NoFeasibleSolutionException
    {
        // make sure we're in Phase 1
        if (!matrix.hasArtificialVariables())
        {
            return;
        }

        while (!isPhase1Solved())
        {
            doIteration();
        }

        // if W is not zero then we have no feasible solution
        if (!MathUtils.equals(matrix.getEntry(0, matrix.getRhsOffset()), 0, epsilon))
        {
            throw new NoFeasibleSolutionException();
        }
    }

    /**
     * Iterates until the optimal solution is arrived at.
     * 
     * @throws UnboundedSolutionException
     *             if the model is found not to have a bounded solution
     * @throws NoFeasibleSolutionException
     *             if there is no feasible solution
     */
    public SimplexResult solve() throws UnboundedSolutionException, NoFeasibleSolutionException
    {
        matrix.print(true);
        solvePhase1();
        matrix.discardArtificialVariables();
        while (!isOptimal())
        {
            doIteration();
        }
        matrix.print(false);
        return matrix.getSolution();
    }

}
